/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Lily
 * Date: 2024-10-08
 * Time: 12:51
 */
public class findTarget_SumWays {
    int sum = 0;
    int aim = 0;

    public int findTargetSumWays(int[] nums, int target) {
        aim = target;
        findTarget_SumWays_dfs(nums, 0, 0);
        return sum;
    }

    private void findTarget_SumWays_dfs(int[] nums, int pos, int path) {
        if (nums.length == pos) {
            if (aim == path) {
                sum++;
            }
            return;
        }
        findTarget_SumWays_dfs(nums, pos + 1, path + nums[pos]);
        findTarget_SumWays_dfs(nums, pos + 1, path - nums[pos]);
    }
}
